package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC940 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {

        int factor = 1000000007;

        public int distinctSubseqII(String s) {
            final int n = s.length();
            long[] dp = new long[n + 1];
            int[] last = new int[26];
            Arrays.fill(last, -1);
            dp[0] = 1;

            for (int i = 0; i < n; i++) {
                int ch = s.charAt(i) - 'a';
                dp[i + 1] = (dp[i] * 2 - (last[ch] == -1 ? 0 : dp[last[ch]])) % factor;
                last[ch] = i;
            }

            return (int) ((dp[n] - 1 + factor) % factor);
        }
    }

    public void run() {
//        System.out.println(new Solution().distinctSubseqII("abc"));
//        System.out.println(new Solution().distinctSubseqII("aba"));
//        System.out.println(new Solution().distinctSubseqII("aaa"));
        System.out.println(new Solution().distinctSubseqII("blljuffdyfrkqtwfyfztpdiyktrhftgtabxxoibcclbjvirnqyynkyaqlxgyybkgyzvcahmytjdqqtctirnxfjpktxmjkojlvvrr"));
    }

    public static void main(String[] args) throws Exception {
        LC940 an = new LC940();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
